package basic;
//判断  单链表  是否回文
public class chapter6 {
    static class listNode{
        public int val;
        public listNode next;
        public listNode(int x){
            val = x;
            next = null;
        }
        public listNode(){
            next = null;
        }
    }

    public static void  main(String[] args) {
        listNode h1 = new listNode();
        listNode h2 = new listNode(1);
        listNode h3 = new listNode(2);
        listNode h4 = new listNode(3);
        listNode h5 = new listNode(4);
        listNode h6 = new listNode(5);
//        listNode h7 = new listNode(1);
        h1.next = h2;
        h2.next = h3;
        h3.next = h4;
        h4.next = h5;
        h5.next = h6;
        h6.next = null;
//        h6.next = h7;
//        h7.next = null;
//        System.out.println(check(h1));
        print(backword(h1));
    }

    static boolean check(listNode head) {
        if(head == null || head.next == null) {
            return true;
        }
        listNode prev = null;
        listNode fast = head;
        listNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            listNode next = slow.next;
            slow.next = prev;
            prev = slow;
            slow = next;
        }
        //偶数个
        if(fast != null){
            listNode next = slow.next;
            slow.next = prev;
            prev = slow;
            slow = next;
        } else {
            slow = slow.next;
        }

        while(slow != null) {
            System.out.println("slow "+slow.val);
            System.out.println("prev "+prev.val );
            if(slow.val != prev.val) {
                return false;
            }
            slow = slow.next;
            prev = prev.next;
        }
        return true;
    }

    static listNode backword(listNode head) {
        listNode prev = null;
        listNode slow = head;
        int flag = 0;
        //when slow == null, prev是尾
        while (slow != null) {
            listNode next = slow.next;
            slow.next = prev;
            prev = slow;
            slow = next;
            if(flag == 1) {
                prev.next = null;
            }
            flag++;
        }
        slow = new listNode();
        slow.next = prev;
        return slow;
    }

    static void print(listNode head){
        System.out.print("head ");
        while(head.next != null) {
            System.out.print(head.next.val+" ");
            head = head.next;
        }
    }
}
